package com.cd.algorithm.order.code;

import java.util.Arrays;

/**
 * 希尔排序
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] array = {9, 5, 2, 7, 1, 6, 3, 8, 4};
        System.out.println("Before Sorting:" + Arrays.toString(array));
//        shellSort(array);
        myTestCode(array);
        System.out.println("After Sorting:" + Arrays.toString(array));
    }

    public static void myTestCode(int[] array) {
        int length = array.length;
        int gap;

        for (gap = length / 2; gap > 0; gap /= 2) {//循环范围： gap = 4 2 1
            for (int i = 0; i +gap < length; i++) {
                if(array[i] > array[i+gap]){
                    int temp =array[i];
                    array[i] = array[i+gap];
                    array[i+gap] = temp;
                }
            }
        }
    }

    public static void shellSort(int[] array) {
        int k = 0;
        // 希尔排序的增量序列选择，这里使用的是最简单的序列：原始序列长度的一半，每次减半
        // 在实际应用中，还可以选择其他更优的序列来提高排序效率
        //假设数组长度为8  循环三次  gap三次的值分别为 4  2  1
        for (int gap = array.length / 2; gap > 0; gap /= 2) {
            // 对于每一个增量值gap gap=4时循环4次 i值为 4 5 6 7
            //                  gap=2时循环5次 i值为 2 3 4 5 6 7
            //                  gap=1时循环6次 i值为 1 2 3 4 5 6 7
            for (int i = gap; i < array.length; i++) {
                // 将元素array[i]插入到已按照gap大小分组并排序好的序列中
                int temp = array[i];
                int j;
                for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                    System.out.println(++k + "最内层");
                    array[j] = array[j - gap]; // 将较大的元素后移
                }
                array[j] = temp; // 将temp（即待插入元素）插入到正确位置
            }
        }

    }
}


